package gold.digger;

import gold.vo.TreeNode;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1530 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        int count = 0;

        public int countPairs(TreeNode root, int distance) {
            countPairsRecur(root, distance);
            return count;
        }

        public void countPairsRecur(TreeNode root, int distance) {
            if (null == root) return;
            List<Integer> leftList = getLeafDistanceList(root.left, 0);
            List<Integer> rightList = getLeafDistanceList(root.right, 0);
            for (Integer leftDist : leftList) {
                for (Integer rightDist : rightList) {
                    if (leftDist + rightDist <= distance) ++count;
                }
            }
            countPairsRecur(root.left, distance);
            countPairsRecur(root.right, distance);
        }


        List<Integer> getLeafDistanceList(TreeNode root, int curDistance) {
            List<Integer> list = new ArrayList<>();
            if (null == root) return list;
            if (null == root.left && null == root.right) {
                list.add(curDistance + 1);
                return list;
            }

            List<Integer> leftList = getLeafDistanceList(root.left, curDistance + 1);
            List<Integer> rightList = getLeafDistanceList(root.right, curDistance + 1);
            list.addAll(leftList);
            list.addAll(rightList);
            return list;
        }

    }

    public void run() {
        Solution solution = new Solution();
        TreeNode root = TreeNode.createTree("1,2,3,4,5,6,7");
        System.out.println(solution.countPairs(root, 3));
    }

    public static void main(String[] args) throws Exception {
        LC1530 an = new LC1530();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
